package com.chapter2.sort;

/** 
 * @ClassName: ShellSort 
 * @Description: 希尔排序
 * @author minjun minjun@bw30.com
 * @date 2015-2-13 下午11:23:28 
 *  
 */
public class ShellSort extends AbstractSort {

	/**
	 * 希尔排序其实就是对插入排序的一种优化
	 * 
	 * 由于插入排序在对几乎顺序的数组进行排序时非常快，时间复杂度可达到O(N)。
	 * 利用这个特点，希尔排序的想法是
	 * 1.将一整个数组元素拆分成间隔较大的小数组（序列）,然后对他们进行插入排序，这样可以减少比较和换位的时间
	 * 2.多次这个拆分之后，间隔会变小，但是这时已经排成了一个大体顺序的数组，之后再利用插入排序的时候速度会越来越快
	 * 
	 * 基于以上两点，选择基于插入排序的希尔排序，是可以非常好的利用插入排序的特点
	 * 
	 * 以下利用knuth优化后的希尔排序最差的情况下时间复杂度也在O(N3/2)以内。对于数量中等的数组，如果图代码简单方便，希尔排序是个不错的选择
	 */
	@Override
	public void sort(int[] array) {
		int len=array.length;
		int d=1;
		//选择希尔排序的时候步长（间隔）的选取非常重要，一般情况都喜欢选择len/2作为步长。
		//但是这样容易导致的情况就是会使得要么就是一直都奇数位置和奇数位置作比较，要么就是偶数位置和偶数位置做比较，得到最后间隔为1的时候才拿奇数偶数位置比较，这样最后插入排序的时候性能会很糟糕
		//这里利用knuth的3d+1原则
		while(d<len/3) d=d*3+1;
		while(d>=1){
			//利用插入排序
			for(int i=d;i<len;i++){
				for(int j=i;j>=d&&less(array[j], array[j-d]);j-=d){
					exchange(array, j, j-d);
				}
			}
			d/=3;
		}
	}

}
